package arraytraversal;


/**
 * 
 * @author Qu huanwen
 *
 */
public class ArrayTraversal {

    /**
     * @param args
     */

    public static void main(String[] args) {
        ArrayTraversal t = new ArrayTraversal();
        printArray(t.traverse(new int[][] { { 1, 2, 3 }, { 4, 5, 6 },
                { 7, 8, 9 } }, 3, 3));
        printArray(t.traverse(new int[][] { { 1, 2, 3 }, { 4, 5, 6 },
                { 7, 8, 9 }, { 10, 11, 12 } }, 4, 3));

    }

    static private void printArray(int[] a) {
        for (int i : a) {

            System.out.print(i + " ");
        }
        System.out.println();
    }

    public int[] traverse(int[][] a, int rows, int cols) {
        int[] r = new int[rows * cols];
        int n = 0;

        int row = 0, col = 0;
        boolean up = true;
        while (row < rows && col < cols) {
            r[n++] = a[row][col];
            if (up && row - 1 >= 0 && col + 1 < cols) {
                row -= 1;
                col += 1;
            } else if (!up && row + 1 < rows && col - 1 >= 0) {
                row += 1;
                col -= 1;
            } else {
                if (row > col) {
                    if (row + 1 < rows)
                        row += 1; // down
                    else
                        col += 1; // right
                } else {
                    if (col + 1 < cols)
                        col += 1; // right
                    else
                        row += 1; // down
                }
                up = !up;
            }
        }
        return r;
    }

}
